package leetcode.code2497;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.stream.Stream;

import javax.xml.transform.stream.StreamSource;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {
	


	public int maxStarSum(int[] vals, int[][] edges, int k) {
		int n = vals.length;
		int[] sums = new int[n];// 各个点的星和
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < n; i++) {
			max = Math.max(max, vals[i]);
			sums[i] = vals[i];
		}
		if (k == 0) {
			return max;
		}
		List<PriorityQueue<Integer>> nexts = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			nexts.add(new PriorityQueue<>());
		}
		int ans = max;
		for (int[] e : edges) {
			int a = e[0], b = e[1];
			int va = vals[a], vb = vals[b];
			if (nexts.get(a).size() < k && vb > 0) {
				nexts.get(a).add(vb);
				sums[a] += vb;
			} else if (nexts.get(a).size() == k && nexts.get(a).peek() < vb) {
				sums[a] += vb;
				sums[a] -= nexts.get(a).poll();
				nexts.get(a).add(vb);
			}
			if (nexts.get(b).size() < k && va > 0) {
				nexts.get(b).add(va);
				sums[b] += va;
			} else if (nexts.get(b).size() == k && nexts.get(b).peek() < va) {
				sums[b] += va;
				sums[b] -= nexts.get(b).poll();
				nexts.get(b).add(va);
			}
			ans = Math.max(ans, sums[a]);
			ans = Math.max(ans, sums[b]);
		}
		return ans;
	}



	@Override
	public void debug4() {
		H.compare(62, this.maxStarSum(H.str2array3("[0,-36,4,35,27,-13]"), H.str2array1("[[5,3],[4,3],[0,4],[2,4],[0,2]]"), 1));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}

